//
// Created by shenbin on 2022/5/7.
//

#ifndef ALGORITHM_TRAINNING_C04_LC46_H
#define ALGORITHM_TRAINNING_C04_LC46_H

#include <vector>

using namespace std;

class LeetCode46 {
public:
    vector<vector<int>> permute(vector<int> &nums) {
        this->n = nums.size();
        this->used = vector<bool>(n, false);
        recur(nums, 0);
        return ans;

    }

private:
    vector<bool> used;
    vector<vector<int>> ans;
    vector<int> a;
    int n;

    void recur(vector<int> &nums, int pos) {
        if (pos == n) {
            ans.push_back(a);
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                a.push_back(nums[i]);
                used[i] = true;
                recur(nums, pos + 1);
                used[i] = false;
                a.pop_back();
            }
        }
    }
};

#endif //ALGORITHM_TRAINNING_C04_LC46_H
